{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #K Closest Points to Origin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #array #math #divide-and-conquer #quickselect #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数组 #数学 #分治 #快速选择 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kClosest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最接近原点的 K 个点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个数组 <code>points</code>&nbsp;，其中&nbsp;<code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>&nbsp;表示 <strong>X-Y</strong> 平面上的一个点，并且是一个整数 <code>k</code> ，返回离原点 <code>(0,0)</code> 最近的 <code>k</code> 个点。</p>\n",
    "\n",
    "<p>这里，平面上两点之间的距离是&nbsp;<strong>欧几里德距离</strong>（&nbsp;<code>√(x<sub>1</sub>&nbsp;- x<sub>2</sub>)<sup>2</sup>&nbsp;+ (y<sub>1</sub>&nbsp;- y<sub>2</sub>)<sup>2</sup></code>&nbsp;）。</p>\n",
    "\n",
    "<p>你可以按 <strong>任何顺序</strong> 返回答案。除了点坐标的顺序之外，答案 <strong>确保</strong> 是 <strong>唯一</strong> 的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/03/03/closestplane1.jpg\" style=\"height: 400px; width: 400px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[1,3],[-2,2]], k = 1\n",
    "<strong>输出：</strong>[[-2,2]]\n",
    "<strong>解释： </strong>\n",
    "(1, 3) 和原点之间的距离为 sqrt(10)，\n",
    "(-2, 2) 和原点之间的距离为 sqrt(8)，\n",
    "由于 sqrt(8) &lt; sqrt(10)，(-2, 2) 离原点更近。\n",
    "我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[3,3],[5,-1],[-2,4]], k = 2\n",
    "<strong>输出：</strong>[[3,3],[-2,4]]\n",
    "（答案 [[-2,4],[3,3]] 也会被接受。）\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= points.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup>&nbsp;&lt; x<sub>i</sub>, y<sub>i</sub>&nbsp;&lt; 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [k-closest-points-to-origin](https://leetcode.cn/problems/k-closest-points-to-origin/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [k-closest-points-to-origin](https://leetcode.cn/problems/k-closest-points-to-origin/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,3],[-2,2]]\\n1', '[[3,3],[5,-1],[-2,4]]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:\n",
    "        # dis_list = {}\n",
    "        # res = []\n",
    "        # final_len = K\n",
    "        # for point in points:\n",
    "        #     dis = abs(point[0])**2 + abs(point[1]) ** 2\n",
    "        #     dis_list[dis] = dis_list.get(dis, [])\n",
    "        #     dis_list[dis].append(point)\n",
    "        # for key in sorted(list(dis_list.keys()))[:K]:\n",
    "        #     temp_points = dis_list[key]\n",
    "        #     append_num = min(len(temp_points), K)\n",
    "        #     K = K - append_num\n",
    "        #     res += temp_points[:append_num]\n",
    "        #     if len(res) == final_len:\n",
    "        #         return res\n",
    "        points.sort(key = lambda P: P[0]**2 + P[1]**2)\n",
    "        return points[:K]\n",
    "    \n",
    "#         dist = lambda i: points[i][0]**2 + points[i][1]**2\n",
    "\n",
    "#         def sort(i, j, K):\n",
    "#             # Partially sorts A[i:j+1] so the first K elements are\n",
    "#             # the smallest K elements.\n",
    "#             if i >= j: return\n",
    "\n",
    "#             # Put random element as A[i] - this is the pivot\n",
    "#             k = random.randint(i, j)\n",
    "#             points[i], points[k] = points[k], points[i]\n",
    "\n",
    "#             mid = partition(i, j)\n",
    "#             if K < mid - i + 1:\n",
    "#                 sort(i, mid - 1, K)\n",
    "#             elif K > mid - i + 1:\n",
    "#                 sort(mid + 1, j, K - (mid - i + 1))\n",
    "\n",
    "#         def partition(i, j):\n",
    "#             # Partition by pivot A[i], returning an index mid\n",
    "#             # such that A[i] <= A[mid] <= A[j] for i < mid < j.\n",
    "#             oi = i\n",
    "#             pivot = dist(i)\n",
    "#             i += 1\n",
    "\n",
    "#             while True:\n",
    "#                 while i < j and dist(i) < pivot:\n",
    "#                     i += 1\n",
    "#                 while i <= j and dist(j) >= pivot:\n",
    "#                     j -= 1\n",
    "#                 if i >= j: break\n",
    "#                 points[i], points[j] = points[j], points[i]\n",
    "\n",
    "#             points[oi], points[j] = points[j], points[oi]\n",
    "#             return j\n",
    "\n",
    "#         sort(0, len(points) - 1, K)\n",
    "#         return points[:K]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points, K):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :type K: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        points.sort(key = lambda x: (x[0]**2 + x[1]**2) ** 0.5)\n",
    "        n = len(points) - K\n",
    "        if n < 0:\n",
    "            n = 0\n",
    "        for i in range(n):\n",
    "            points.pop();\n",
    "        return points"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points, K):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :type K: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        points.sort(key=lambda a:a[0]**2+a[1]**2)\n",
    "        return points[:K]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points, K):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :type K: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        dis = []\n",
    "        for i in points:\n",
    "            dis.append((i[0]**2+i[1]**2,i))\n",
    "        # heap = dis[:K]\n",
    "        # for i in range(K,len(dis)):\n",
    "        #     j = len(heap)-1\n",
    "        #     while j>0:\n",
    "        #         k = j\n",
    "        #         while k>0:\n",
    "        #             if heap[k][0]>heap[(k-1)>>1][0]:\n",
    "        #                 heap[k],heap[(k-1)>>1] = heap[(k-1)>>1],heap[k]\n",
    "        #             k = (k-1)>>1\n",
    "        #         j-=1\n",
    "        #     if heap[0][0]>dis[i][0]:\n",
    "        #         heap.pop(0)\n",
    "        #         heap.append(dis[i])\n",
    "        # return [i[1] for i in heap]\n",
    "        dis.sort()\n",
    "        return [dis[i][1] for i in range(K)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points, K):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :type K: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        dist = lambda i: points[i][0]**2 + points[i][1]**2\n",
    "\n",
    "        def work(i, j, K):\n",
    "            if i >= j: return\n",
    "            oi, oj = i, j\n",
    "            pivot = dist(random.randint(i, j))\n",
    "            while i < j:\n",
    "                while i < j and dist(i) < pivot: i += 1\n",
    "                while i < j and dist(j) > pivot: j -= 1\n",
    "                points[i], points[j] = points[j], points[i]\n",
    "\n",
    "            if K <= i - oi + 1:\n",
    "                work(oi, i, K)\n",
    "            else:\n",
    "                work(i+1, oj, K - (i - oi + 1))\n",
    "\n",
    "        work(0, len(points) - 1, K)\n",
    "        return points[:K]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: 'List[List[int]]', K: 'int') -> 'List[List[int]]':\n",
    "        a=[(i[0]**2+i[1]**2,i) for i in points]\n",
    "        # print(a)\n",
    "        a.sort(key=lambda i:i[0])\n",
    "        # print(a)\n",
    "        return [i[1] for i in a[:K]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points, K):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :type K: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        ans = []\n",
    "        h = list(map(lambda x: (x[0] ** 2 + x[1] ** 2, x), points))\n",
    "        heapq.heapify(h)\n",
    "        for i in range(K):\n",
    "            ans.append(heapq.heappop(h)[1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def kClosest(self, points, K):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :type K: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        return heapq.nsmallest(K, points, lambda p: p[0]**2 + p[1]**2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: 'List[List[int]]', K: 'int') -> 'List[List[int]]':\n",
    "        dist = []\n",
    "        for point in points:\n",
    "            d = point[0]**2 + point[1]**2\n",
    "            dist.append(d)\n",
    "        result = heapq.nsmallest(K, points, lambda p: p[0]**2 + p[1]**2)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def kClosest(self, points, K):\n",
    "        dist = lambda i: points[i][0]**2 + points[i][1]**2\n",
    "\n",
    "        def work(i, j, K):\n",
    "            if i >= j: return\n",
    "            oi, oj = i, j\n",
    "            pivot = dist(random.randint(i, j))\n",
    "            while i < j:\n",
    "                while i < j and dist(i) < pivot: i += 1\n",
    "                while i < j and dist(j) > pivot: j -= 1\n",
    "                points[i], points[j] = points[j], points[i]\n",
    "\n",
    "            if K <= i - oi + 1:\n",
    "                work(oi, i, K)\n",
    "            else:\n",
    "                work(i+1, oj, K - (i - oi + 1))\n",
    "\n",
    "        work(0, len(points) - 1, K)\n",
    "        return points[:K]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: 'List[List[int]]', K: 'int') -> 'List[List[int]]':\n",
    "        if not points:\n",
    "            return\n",
    "        def distance(point):\n",
    "            return point[0] ** 2 + point[1] ** 2\n",
    "        ans = points[:K]\n",
    "        ans.sort(key=lambda x: x[0] ** 2 + x[1] ** 2)\n",
    "        for point in points[K:]:\n",
    "            # print(ans)\n",
    "            if distance(point) < distance(ans[-1]):\n",
    "                ans.pop()\n",
    "                if not ans:\n",
    "                    ans = [point]\n",
    "                    continue\n",
    "                if distance(point) < distance(ans[0]):\n",
    "                    ans = [point] + ans\n",
    "                    continue\n",
    "                elif distance(point) > distance(ans[-1]):\n",
    "                    ans = ans + [point]\n",
    "                    continue\n",
    "                else:\n",
    "                    l = 0\n",
    "                    r = K - 1\n",
    "                    while l < r:\n",
    "                        mid = (l + r) // 2\n",
    "                        if distance(point) < distance(ans[mid]):\n",
    "                            r = mid - 1\n",
    "                        else:\n",
    "                            l = mid + 1\n",
    "                if distance(point) > distance(ans[l]):\n",
    "                    ans = ans[:l+1] + [point] + ans[l+1:]\n",
    "                else:\n",
    "                    ans = ans[:l] + [point] + ans[l:]\n",
    "                 \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: 'List[List[int]]', K: 'int') -> 'List[List[int]]':\n",
    "        points = sorted(points, key = distance)\n",
    "        ans = []\n",
    "        for i in range(K):\n",
    "            ans.append(points[i])\n",
    "        return ans\n",
    "\n",
    "def distance(point):\n",
    "    x = point[0]\n",
    "    y = point[1]\n",
    "    # 开不开根无所谓\n",
    "    dis = x ** 2 + y ** 2\n",
    "    return dis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points, K):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :type K: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        a = sorted(points, key=lambda x:pow(x[0],2)+pow(x[1],2))\n",
    "        return a[:K]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def kClosest(self, points, K):\n",
    "        dist = lambda i: points[i][0]**2 + points[i][1]**2\n",
    "\n",
    "        def work(i, j, K):\n",
    "            if i >= j: return\n",
    "            oi, oj = i, j\n",
    "            pivot = dist(random.randint(i, j))\n",
    "            while i < j:\n",
    "                while i < j and dist(i) < pivot: i += 1\n",
    "                while i < j and dist(j) > pivot: j -= 1\n",
    "                points[i], points[j] = points[j], points[i]\n",
    "\n",
    "            if K <= i - oi + 1:\n",
    "                work(oi, i, K)\n",
    "            else:\n",
    "                work(i+1, oj, K - (i - oi + 1))\n",
    "\n",
    "        work(0, len(points) - 1, K)\n",
    "        return points[:K]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points, K):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :type K: int\n",
    "        :rtype: List[List[int]]\n",
    "        #二分法\n",
    "        \"\"\"\n",
    "        def rank(length, res):\n",
    "            if len(res) == 1:\n",
    "                if length > res[0]:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            # if length <= min(res):\n",
    "            #     return 0\n",
    "            # elif length >= max(res):\n",
    "            #     return len(res)\n",
    "            lo = 0\n",
    "            hi = len(res)\n",
    "            mid = (lo + hi) // 2\n",
    "            while (lo < hi):\n",
    "                if length == res[mid]:\n",
    "                    return mid\n",
    "                elif length < res[mid]:\n",
    "                    hi = mid\n",
    "                else:\n",
    "                    lo = mid + 1\n",
    "                mid = (lo + hi) // 2\n",
    "            return mid\n",
    "\n",
    "        res_l = []\n",
    "        res_raw = []\n",
    "        if K == 0:\n",
    "            return res_raw\n",
    "        if not points:\n",
    "            return res_raw\n",
    "\n",
    "        for each in points:\n",
    "            if not res_raw:\n",
    "                res_l = [each[0] ** 2 + each[1] ** 2]\n",
    "                res_raw = [each]\n",
    "            else:\n",
    "                length = each[0] ** 2 + each[1] ** 2\n",
    "                index = rank(length, res_l)\n",
    "                res_raw.insert(index, each)\n",
    "                res_l.insert(index, length)\n",
    "        return res_raw[:K]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points, K):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :type K: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        sqrts = {index:(i[0]**2+i[1]**2) for index,i in enumerate(points)}\n",
    "        nsqrts = sorted(sqrts.items(),key=lambda x:x[1])\n",
    "        out = []\n",
    "        for i in range(K):\n",
    "            out.append(points[nsqrts[i][0]])\n",
    "        return out\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points, K):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :type K: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        dist = []\n",
    "        for point in points:\n",
    "            dist.append(point[0]*point[0] + point[1]*point[1])\n",
    "        sdist = sorted(dist)\n",
    "        kvalue = sdist[K-1]\n",
    "        res = []\n",
    "        for ind,value in enumerate(dist):\n",
    "            if value <= kvalue:\n",
    "                res.append(points[ind])\n",
    "        \n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points, K):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :type K: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        init = [0, 0]\n",
    "        points_dict = dict()\n",
    "        dist = []\n",
    "        ans = []\n",
    "        for i in points:\n",
    "            temp = []\n",
    "            for j in range(0,2):\n",
    "                temp.append((init[j] - i[j]) ** 2)\n",
    "            temp = sum(temp) ** 0.5\n",
    "            dist.append(temp)\n",
    "        for k in range(len(dist)):\n",
    "            points_dict[dist[k]] = points[k]\n",
    "        dist_sort = sorted(points_dict.keys())\n",
    "        for l in range(K):\n",
    "            ans.append(points_dict[dist_sort[l]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points, K):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :type K: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        d = {}\n",
    "        dis=[]\n",
    "        dis1=[]\n",
    "        res=[]\n",
    "        for i, item in enumerate(points):\n",
    "            dis.append(item[0]**2 +item[1]**2)\n",
    "            dis1.append(item[0]**2 +item[1]**2) \n",
    "        dis.sort()\n",
    "\n",
    "        for i in range(K):\n",
    "            k=dis1.index(dis[i])\n",
    "            res.append(points[k])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=973 lang=python3\n",
    "#\n",
    "# [973] 戳印序列\n",
    "#\n",
    "# https://leetcode-cn.com/problems/k-closest-points-to-origin/description/\n",
    "#\n",
    "# algorithms\n",
    "# Easy (65.58%)\n",
    "# Total Accepted:    1.7K\n",
    "# Total Submissions: 2.6K\n",
    "# Testcase Example:  '[[1,3],[-2,2]]\\n1'\n",
    "#\n",
    "# 我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。\n",
    "# \n",
    "# （这里，平面上两点之间的距离是欧几里德距离。）\n",
    "# \n",
    "# 你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。\n",
    "# \n",
    "# \n",
    "# \n",
    "# 示例 1：\n",
    "# \n",
    "# 输入：points = [[1,3],[-2,2]], K = 1\n",
    "# 输出：[[-2,2]]\n",
    "# 解释： \n",
    "# (1, 3) 和原点之间的距离为 sqrt(10)，\n",
    "# (-2, 2) 和原点之间的距离为 sqrt(8)，\n",
    "# 由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。\n",
    "# 我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。\n",
    "# \n",
    "# \n",
    "# 示例 2：\n",
    "# \n",
    "# 输入：points = [[3,3],[5,-1],[-2,4]], K = 2\n",
    "# 输出：[[3,3],[-2,4]]\n",
    "# （答案 [[-2,4],[3,3]] 也会被接受。）\n",
    "# \n",
    "# \n",
    "# \n",
    "# \n",
    "# 提示：\n",
    "# \n",
    "# \n",
    "# 1 <= K <= points.length <= 10000\n",
    "# -10000 < points[i][0] < 10000\n",
    "# -10000 < points[i][1] < 10000\n",
    "# \n",
    "# \n",
    "#\n",
    "class Solution:\n",
    "    def kClosest(self, points, K):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :type K: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        mapping = {}\n",
    "        for p in points:\n",
    "            mapping[(p[0],p[1])] = p[0] ** 2 + p[1] ** 2\n",
    "        m = sorted(mapping, key = lambda x: mapping[x])\n",
    "        ans = []\n",
    "        for i in range(K):\n",
    "            ans.append([m[i][0],m[i][1]])\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points, K):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :type K: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        for point in points:\n",
    "            result.append(point[0]**2 + point[1]**2)\n",
    "        t = sorted(range(len(result)), key=lambda k: result[k])\n",
    "        temp = []\n",
    "        for i in range(K):\n",
    "            temp.append(points[t[i]])\n",
    "        return temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import math\n",
    "    def kClosest(self, points: 'List[List[int]]', K: 'int') -> 'List[List[int]]':\n",
    "        points.sort(key = lambda P: P[0]**2 + P[1]**2)\n",
    "        return points[:K]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:\n",
    "        '''\n",
    "        points.sort(key=lambda P:P[0]**2+P[1]**2)\n",
    "        return points[:K]\n",
    "        '''\n",
    "        distance = lambda i: points[i][0] ** 2 + points[i][1] ** 2\n",
    "        def work(i, j, K):\n",
    "            if i > j:\n",
    "                return\n",
    "            oi, oj = i, j\n",
    "            pivot = distance(oi)\n",
    "            while i != j:\n",
    "                while i < j and distance(j) >= pivot:\n",
    "                    j -= 1\n",
    "                while i < j and distance(i) <= pivot:\n",
    "                    i += 1\n",
    "                if i < j:\n",
    "                    points[i], points[j] = points[j], points[i] \n",
    "            points[i], points[oi] = points[oi], points[i]\n",
    "            if K <= i - oi + 1:\n",
    "                work(oi, i - 1, K)\n",
    "            else:\n",
    "                work(i + 1, oj, K - (i - oi + 1))   \n",
    "        work(0, len(points) - 1, K)\n",
    "        return points[:K]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:\n",
    "        comparator = lambda point: point[0]**2 + point[1]**2\n",
    "        points.sort(key=comparator)\n",
    "        return points[:K]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        4. 分治法，借用快排的思想\n",
    "        因为需要从O(nlogn)进一步优化，只能借助于题目中不需要返回结果有序。\n",
    "        但是前面的方案中其实是保证了有序的。\n",
    "            * 用一个partition(i, j, K)的方法来实现：最小的K个points出现在头部\n",
    "            * pivot: 使得 pivot 两边分别小于和大于pivot对应的distance\n",
    "        \"\"\"\n",
    "        if not points:\n",
    "            return []\n",
    "        distance = lambda idx: points[idx][0] ** 2 + points[idx][1] ** 2\n",
    "\n",
    "        # in-place partition points\n",
    "        def partition(i, j, K) -> None:\n",
    "            if i > j:\n",
    "                return\n",
    "            oi, oj = i, j\n",
    "            # randomly choose pivot and swap with pivot.\n",
    "            pivot_idx = random.randint(i, j)\n",
    "            points[oi], points[pivot_idx] = points[pivot_idx], points[oi]\n",
    "            pivot = distance(oi)\n",
    "            while i < j:\n",
    "                # 先进行右半边\n",
    "                while i < j and distance(j) >= pivot:\n",
    "                    j -= 1\n",
    "                while i < j and distance(i) <= pivot:\n",
    "                    i += 1\n",
    "                if i < j:\n",
    "                    # otherwise swap points[i], points[j]\n",
    "                    points[i], points[j] = points[j], points[i]\n",
    "            \n",
    "            points[i], points[oi] = points[oi], points[i]\n",
    "            # if left_length, i.e: i-oi+1 >= k, partition on left side\n",
    "            # otherwise left half is ok, partition on right side\n",
    "            if i - oi + 1 >= K:\n",
    "                partition(oi, i-1, K)\n",
    "            else:\n",
    "                partition(i+1, oj, K-(i-oi+1))\n",
    "        \n",
    "        partition(0, len(points)-1, K)\n",
    "        return points[:K]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        3. 小根堆，直接构建大小为N的小根堆，然后依次pop出最小的K个即可\n",
    "        O(nlogn)\n",
    "        \"\"\"\n",
    "        if not points:\n",
    "            return []\n",
    "        distance = lambda idx: points[idx][0] ** 2 + points[idx][1] ** 2\n",
    "        min_heap = []\n",
    "        for i in range(len(points)):\n",
    "            heapq.heappush(min_heap, (distance(i), points[i]))\n",
    "        res = []\n",
    "        for i in range(K):\n",
    "            res.append(heapq.heappop(min_heap)[1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:\n",
    "        if K > len(points):\n",
    "            return points\n",
    "        d = {} # key:dist, value:[(p0,p0), (p1,p1)]\n",
    "        res = []\n",
    "        for p in points:\n",
    "            dist = p[0] ** 2 + p[1]**2\n",
    "            if dist not in d:\n",
    "                d[dist] = [p]\n",
    "            else:\n",
    "                d[dist].append(p)\n",
    "\n",
    "        import heapq\n",
    "        l = list(d.keys())\n",
    "        heapq.heapify(l)\n",
    "\n",
    "        while len(res) < K:\n",
    "            idx = heapq.heappop(l)\n",
    "            for item in d[idx]:\n",
    "                res.append(item)        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:\n",
    "        points.sort(key=lambda x:(x[0]**2+x[1]**2))\n",
    "        res = []\n",
    "        for i in range(K):\n",
    "            res.append(points[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:\n",
    "        points.sort(key = lambda x :x[0]**2 + x[1]**2)\n",
    "        return points[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:\n",
    "        def random_select(left: int, right: int, k: int):\n",
    "            pivot_id = random.randint(left, right)\n",
    "            pivot = points[pivot_id][0] ** 2 + points[pivot_id][1] ** 2\n",
    "            points[right], points[pivot_id] = points[pivot_id], points[right]\n",
    "            i = left - 1\n",
    "            for j in range(left, right):\n",
    "                if points[j][0] ** 2 + points[j][1] ** 2 <= pivot:\n",
    "                    i += 1\n",
    "                    points[i], points[j] = points[j], points[i]\n",
    "            i += 1\n",
    "            points[i], points[right] = points[right], points[i]\n",
    "            # [left, i-1] 都小于等于 pivot, [i+1, right] 都大于 pivot\n",
    "            if k < i - left + 1:\n",
    "                random_select(left, i - 1, k)\n",
    "            elif k > i - left + 1:\n",
    "                random_select(i + 1, right, k - (i - left + 1))\n",
    "\n",
    "        n = len(points)\n",
    "        random_select(0, n - 1, k)\n",
    "        return points[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        topk 问题，可以用期望为线性的快速选择算法来完成，读懂题意：前 k 个问题\n",
    "        :param points:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        def distance(i: int):\n",
    "            return points[i][0] ** 2 + points[i][1] ** 2\n",
    "\n",
    "        def swap(i: int, j: int):\n",
    "            points[i], points[j] = points[j], points[i]\n",
    "\n",
    "        def find(start: int, end: int):\n",
    "            pivot_idx = random.randint(start, end)\n",
    "            pivot_val = distance(pivot_idx)\n",
    "            swap(pivot_idx, end)\n",
    "            pivot_idx = end\n",
    "            idx = start - 1\n",
    "            for i in range(start, end):\n",
    "                if distance(i) <= pivot_val:\n",
    "                    idx += 1\n",
    "                    swap(i, idx)\n",
    "                    if pivot_idx == idx:\n",
    "                        pivot_idx = i\n",
    "            idx += 1\n",
    "            swap(idx, pivot_idx)\n",
    "            return idx\n",
    "\n",
    "        def select(start: int, end: int, target: int) -> List[List[int]]:\n",
    "            if end < start:\n",
    "                return []\n",
    "            pivot = find(start, end)\n",
    "            if pivot - start > target:\n",
    "                select(start, pivot - 1, target)\n",
    "            else:\n",
    "                select(pivot + 1, end, target - pivot + start - 1)\n",
    "\n",
    "        select(0, len(points) - 1, k)\n",
    "        return points[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:\n",
    "        # q = [(-x ** 2 - y ** 2, i) for i, (x, y) in enumerate(points[:k])]\n",
    "        # heapq.heapify(q)\n",
    "        \n",
    "        # n = len(points)\n",
    "        # for i in range(k, n):\n",
    "        #     x, y = points[i]\n",
    "        #     dist = -x ** 2 - y ** 2\n",
    "        #     heapq.heappushpop(q, (dist, i))\n",
    "        \n",
    "        # ans = [points[identity] for (_, identity) in q]\n",
    "        # return ans\n",
    "        def smaller(a, b):\n",
    "            if a[0]**2 + a[1]**2 < b[0]**2 + b[1]**2:\n",
    "                return True \n",
    "            return False \n",
    "\n",
    "        def heapify(arr, Len, i):\n",
    "            left = 2*i +1\n",
    "            right = 2*i +2 \n",
    "            smallest = i \n",
    "\n",
    "            if left < Len and smaller(arr[left], arr[smallest]):\n",
    "                smallest = left \n",
    "            if right < Len and smaller(arr[right], arr[smallest]):\n",
    "                smallest = right\n",
    "            \n",
    "            if smallest != i:\n",
    "                arr[i], arr[smallest] = arr[smallest], arr[i]\n",
    "                heapify(arr, Len, smallest)\n",
    "        \n",
    "        def build_min_heap(arr):\n",
    "            for i in range(len(arr)//2 -1, -1, -1):\n",
    "                heapify(arr, len(arr), i)\n",
    "        \n",
    "\n",
    "        build_min_heap(points)\n",
    "\n",
    "        print(points)\n",
    "        j = 0\n",
    "        for i in range(len(points)-1, -1, -1):\n",
    "            points[0], points[i] = points[i], points[0]\n",
    "            heapify(points, i, 0)\n",
    "            j += 1 \n",
    "            if j == k:\n",
    "                break \n",
    "        return points[-k:]\n",
    "        \n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    Approach 2.2: Max Heap (user-defined func)\n",
    "    time: O(n) for heapify() in Python, O(nlogk) for adjust\n",
    "    space: O(k)\n",
    "    \"\"\"\n",
    "    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:\n",
    "        n = len(points)\n",
    "        # build the min heap with size of k\n",
    "        self._max_heapify(points, 0, k)\n",
    "\n",
    "        # push the remains to the heap\n",
    "        for i in range(k, n):\n",
    "            if self._dis(points[i]) < self._dis(points[0]):\n",
    "                points[i], points[0] = points[0], points[i]\n",
    "                self._max_heappop(points, 0, k)\n",
    "        return points[:k]\n",
    "\n",
    "    def _max_heapify(self, heap, root, heap_len):\n",
    "        \"\"\"Build a min heap.\"\"\"\n",
    "        for i in range(heap_len-1, -1, root-1):\n",
    "            self._max_heappop(heap, i, heap_len)\n",
    "\n",
    "    def _max_heappop(self, heap, root, heap_len):\n",
    "        \"\"\"Pop the minimum to the top of heap.\"\"\"\n",
    "        cur = root\n",
    "        while cur*2+1 < heap_len:\n",
    "            left, right = cur*2+1, cur*2+2\n",
    "            if heap_len <= right or self._dis(heap[left]) > self._dis(heap[right]):\n",
    "                nex = left\n",
    "            else:\n",
    "                nex = right\n",
    "            if self._dis(heap[cur]) < self._dis(heap[nex]):\n",
    "                heap[cur], heap[nex] = heap[nex], heap[cur]\n",
    "                cur = nex\n",
    "            else:\n",
    "                break\n",
    "\n",
    "    def _dis(self, pair) -> int:\n",
    "        \"\"\"Return the square of Euclidean distance\"\"\"\n",
    "        return pair[0]**2 + pair[1]**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:\n",
    "        c = sorted(points, key=lambda x:x[0]**2+x[1]**2)\n",
    "        return c[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:\n",
    "        return sorted(points,key =  lambda x: x[0]**2 + x[1]**2)[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:\n",
    "        q = [(-x**2-y**2,i) for i ,(x,y) in enumerate(points[:k])]\n",
    "        heapq.heapify(q)\n",
    "        for i in range(k,len(points)):\n",
    "            cur = -points[i][0]**2 - points[i][1]**2\n",
    "            heapq.heappushpop(q,(cur,i))\n",
    "        res  = [points[i] for (_,i)  in q]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:\n",
    "        def random_select(left: int, right: int, k: int):\n",
    "            pivot_id = random.randint(left, right)\n",
    "            pivot = points[pivot_id][0] ** 2 + points[pivot_id][1] ** 2\n",
    "            points[right], points[pivot_id] = points[pivot_id], points[right]\n",
    "            i = left - 1\n",
    "            for j in range(left, right):\n",
    "                if points[j][0] ** 2 + points[j][1] ** 2 >= pivot:\n",
    "                    i += 1\n",
    "                    points[i], points[j] = points[j], points[i]\n",
    "            i += 1\n",
    "            points[i], points[right] = points[right], points[i]\n",
    "            # [left, i-1] 都小于等于 pivot, [i+1, right] 都大于 pivot\n",
    "            if k < i - left + 1:\n",
    "                random_select(left, i - 1, k)\n",
    "            elif k > i - left + 1:\n",
    "                random_select(i + 1, right, k - (i - left + 1))\n",
    "\n",
    "        n = len(points)\n",
    "        if n>k:\n",
    "            random_select(0, n - 1, n-k)\n",
    "        \n",
    "        return points[n-k:n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:\n",
    "        def random_select(left: int, right: int, k: int):\n",
    "            pivot_id = random.randint(left, right)\n",
    "            pivot = points[pivot_id][0] ** 2 + points[pivot_id][1] ** 2\n",
    "            points[right], points[pivot_id] = points[pivot_id], points[right]\n",
    "            i = left - 1\n",
    "            for j in range(left, right):\n",
    "                if points[j][0] ** 2 + points[j][1] ** 2 <= pivot:\n",
    "                    i += 1\n",
    "                    points[i], points[j] = points[j], points[i]\n",
    "            i += 1\n",
    "            points[i], points[right] = points[right], points[i]\n",
    "            # [left, i-1] 都小于等于 pivot, [i+1, right] 都大于 pivot\n",
    "            if k < i - left + 1:\n",
    "                random_select(left, i - 1, k)\n",
    "            elif k > i - left + 1:\n",
    "                random_select(i + 1, right, k - (i - left + 1))\n",
    "        n = len(points)\n",
    "        random_select(0, n - 1, k)\n",
    "        return points[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:\n",
    "        def dist(p):\n",
    "            return p[0] ** 2 + p[1] ** 2\n",
    "        return sorted(points, key=dist)[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:\n",
    "        return nsmallest(k, points, lambda p: p[0] ** 2 + p[1] ** 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:\n",
    "        res=[]\n",
    "        for i in points:\n",
    "            res.append((math.sqrt(pow(i[0],2)+pow(i[1],2)),i))\n",
    "        res.sort()\n",
    "        rest=[]\n",
    "        for i in range(k):\n",
    "            rest.append(res[i][1])\n",
    "        return rest\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:\n",
    "        distances = [(-1 * (x*x + y*y), i)for i, (x, y) in enumerate(points)]\n",
    "        heap = distances[:k]\n",
    "        heapq.heapify(heap)\n",
    "\n",
    "        for i in range(k, len(points)):\n",
    "            heapq.heappushpop(heap, distances[i])\n",
    "        return [points[i] for _,i in heap]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:\n",
    "        distance = []\n",
    "        res = []\n",
    "        for i in range(len(points)):\n",
    "            point = points[i]\n",
    "            dis = point[0]**2 + point[1]**2\n",
    "            distance.append([i, dis])\n",
    "            \n",
    "        distance.sort(key=lambda x:x[1])\n",
    "        \n",
    "        for i in range(k):\n",
    "            res.append(points[distance[i][0]])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:\n",
    "        min_heap = []\n",
    "        for (x, y) in points:\n",
    "            dist = x**2 + y**2\n",
    "            heapq.heappush(min_heap, (dist, [x,y]))\n",
    "\n",
    "        res = []\n",
    "        while k > 0 and min_heap:\n",
    "            res.append(heapq.heappop(min_heap)[1])\n",
    "            k -= 1\n",
    "\n",
    "        return res\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
